#include "huffman_coder.h"

node::node()
{
    left = NULL;
    right = NULL;
}

void node::delete_tree(node *root)
{
    if(root == NULL)
    {
        return;
    }
    delete_tree(root->left);
    delete_tree(root->right);
    delete root;
}

huffman_coder::huffman_coder()
{
    root = NULL;
    data = NULL;
    dedata = NULL;
}

huffman_coder::~huffman_coder()
{
    root->delete_tree(root);
}

void huffman_coder::count_statistic()
{
    //qDebug() << "start statistic";
    int i;
    for (i = 0; i < 2*255+1; i++)
    {
        statistic[i] = 0;
    }
        //qDebug() << "zero memory";
    for (i = 0; i < parameters->bitmap.height*parameters->bitmap.width*3; i++)
    {
        statistic[data[i]+255]++;
    }
}

void huffman_coder::create_tree()
{
    //qDebug() << "prepare data";
    int count = 0;

    node *que[255*2+1];
    node_list *iterator, *list;
    iterator = NULL;
    list = NULL;
    //qDebug() << "create node's";
    for (int i = 0; i < 255*2+1; i++)
    {
        if (statistic[i] != 0)
        {
            /*
            if (iterator == NULL)
                iterator = new node_list;
            else
            {
                iterator->next = new node_list;
                iterator = iterator->next;
            }
            if (list == NULL)
                list = iterator;
            iterator->element = new node;
            iterator->element->value = i-255;
            iterator->element->weight = statistic[i];
            iterator->next = NULL;
            */
            //qDebug() << statistic[i];
            que[count] = new node;
            que[count]->value = i-255;
            que[count]->weight = statistic[i];
            //qDebug() << statistic[i];
            //qDebug() << i-255 << statistic[i] << count;

            count++;
        }
    }
    //for (int i = 0; i < count; i++)
        //qDebug() << que[i]->value << que[i]->weight;
    char_count = count;
    node *small1, *small2, *tree, *tmp, *tmp2;
    //qDebug() << "start creating tree" << count;
    while (count > 1)
    {
        /*
        small1 = list->minimum(NULL);
        small2 = list->minimum(small1);
        list->delete_element(small1);
        list->delete_element(small2);
        qDebug() <<  small1->weight;
        tree = new node;
        tree->left = small1;
        tree->right = small2;
        tree->weight = tree->left->weight+tree->right->weight;
        iterator->next = new node_list;
        iterator = iterator->next;
        iterator->element = tree;
        iterator->next = NULL;
        count--;
        */

        small1 = que[0];
        for (int i = 1; i < count; i++)
            if (small1->weight > que[i]->weight)
                small1 = que[i];
        if (small1 == que[0])
            small2 = que[1];
        else
            small2 = que[0];
        for (int i = 1; i < count; i++)
            if ((small2->weight > que[i]->weight) && (que[i] != small1))
                small2 = que[i];
        /*
        small1 = que[0];
        if (que[1]->weight > small1->weight)
            small2 = que[1];
        else
        {
            small2 = small1;
            small1 = que[1];
        }
        for (int i = 2; i < count; i++)
        {
            if (small1->weight > que[i]->weight)
                small1 = que[i];
            else
            if (small2->weight > que[i]->weight)
                small2 = que[i];
        }
        */
        if (small1->weight > small2->weight)
        {
            tmp2 = small2;
            small2 = small1;
            small1 = tmp2;
        }
        tmp = new node;
        tmp->left = small1;
        tmp->right = small2;
        tmp->weight = tmp->left->weight+tmp->right->weight;
        //if (tmp->weight == 168)
        //qDebug() << small1->weight << small2->weight << tmp->weight << small1 << small2 << tmp;
        int correct = 0;
        for (int i = 0; i < count; i++)
        {
            if ((correct) && (que[i] != tmp->left) && (que[i] != tmp->right))
                que[i-1] = que[i];
            if(que[i] == tmp->left)
            {
                if (correct)
                    que[i-1] = tmp;
                else
                    que[i] = tmp;
                //if (tmp->weight == 168)
                //    qDebug() << i << correct << que[i-1]->weight << que[i]->weight;
            }
            if (que[i] == tmp->right)
            {
                correct = 1;
                //if (tmp->weight == 168)
                    //qDebug() << i << count;
            }
            //qDebug() << correct;
        }
        //qDebug() << "count:" << count;
        count--;
        //qDebug() << count;
        tree = tmp;
        //print_tree(tmp);
    }
    //qDebug() << "root";
    //print_tree(tree, 0, 0);
    root = tree;
    //qDebug() << root->weight;
}

void huffman_coder::make_codes(node *root, int value, short bits)
{
    //qDebug() << value << bits;
    if ((root->left == NULL) && (root->right == NULL))
    {
        code tmp;
        tmp.value = value;
        tmp.bits = bits;
        key[root->value] = tmp;
        //qDebug() << root->value;
    }
    else
    {
        bits++;
        if (root->left != NULL)
            make_codes(root->left, 2*value, bits);
        if (root->right != NULL)
            make_codes(root->right, 2*value+1, bits);
    }
}

void huffman_coder::compress_to_file()
{
    file_saver file;
    file.open(path);
    file.save(parameters->bitmap.width, 8*sizeof(unsigned short));
    file.save(parameters->bitmap.height, 8*sizeof(unsigned short));
    file.save(parameters->compression_type, 8*sizeof(unsigned short));
    if ((parameters->compression_type == 0) || (parameters->compression_type == 1) || (parameters->compression_type == 6))
        file.save(parameters->segment_size, 8*sizeof(unsigned short));
    if ((parameters->compression_type == 0) || (parameters->compression_type == 1))
        for (int i = 0; i < parameters->segment_count*parameters->coefficient_count*3; i++)
            file.save(parameters->coefficients[i], 8*sizeof(unsigned short));
    //file.save(0, 8*sizeof(unsigned short));       //typ kompresji
    file.save(char_count, 8*sizeof(unsigned short));
    //qDebug() << "char count:" << char_count;
    for (int i = 0; i < 2*255+1; i++)
        if (statistic[i] != 0)
        {
            file.save(i, 8*sizeof(short));
            file.save(statistic[i], 8*sizeof(int));
        }
    code tmp;
    for (int i = 0; i < parameters->bitmap.height*parameters->bitmap.width*3; i++)
    {
        tmp = key.value(data[i]);
        //qDebug() << i << data[i] << tmp.value << tmp.bits;
        file.save(tmp.value, tmp.bits);
    }
    //delete data;
    //data = NULL;
    file.close();
}

void huffman_coder::compress(predictor_header *predictor, short *raw_data, QString file)
{
    //qDebug() << "huffman";
    parameters = predictor;
    //delete data;
    data = raw_data;
    path = file;
    key.clear();
    if (root != NULL)
        root->delete_tree(root);
    //qDebug() << "parameters";
    count_statistic();
    //qDebug() << "statistic";
    create_tree();
    //qDebug() << "create tree";
    make_codes(root, 0, 0);
    //qDebug() << "make codes";
    compress_to_file();
}

void huffman_coder::print_tree(node *root, int value, short bits)
{
    if ((root->left == NULL) && (root->right == NULL))
    {
        qDebug() << root->value << value << bits;
    }
    else
    {
        bits++;
        if (root->left != NULL)
            print_tree(root->left, 2*value, bits);
        if (root->right != NULL)
            print_tree(root->right, 2*value+1, bits);
    }
}

node *node_list::minimum(node *no)
{
    int min;
    node *mini;
    node_list *iterator;
    if (this->element != no)
    {
        min = this->element->weight;
        mini = this->element;
        iterator = next;
    }
    else
    {
        iterator = next;
        min = iterator->element->weight;
        mini = iterator->element;
    }
    while (iterator != NULL)
    {
        if (iterator->element->weight < min)
        {
            if(iterator->element != no)
            {
                min = iterator->element->weight;
                mini = iterator->element;
            }
        }
        iterator = next;
    }
    return mini;
}

void node_list::delete_element(node *del)
{
    node_list *iterator = this;
    node_list *tmp;
    while (iterator != NULL)
    {
        if (iterator->next->element == del)
        {
            tmp = iterator->next;
            iterator->next = tmp->next;
            delete tmp;
        }
        else
            iterator = iterator->next;
    }
}

void huffman_coder::decompress_from_file()
{
    file_reader file;
    file.open(path);
    //qDebug() << "open";
    parameters->bitmap.width = file.get(8*sizeof(unsigned short));
    parameters->bitmap.height = file.get(8*sizeof(unsigned short));
    //qDebug() << "size";
    parameters->compression_type = file.get(8*sizeof(unsigned short));
    if ((parameters->compression_type == 0) || (parameters->compression_type == 1) || (parameters->compression_type == 6))
        parameters->segment_size = file.get(8*sizeof(unsigned short));
    //qDebug() << "segment size";
    if ((parameters->compression_type == 0) || (parameters->compression_type == 1))
    {
        parameters->segment_count = (ceil((double)parameters->bitmap.height/(double)parameters->segment_size))*ceil((double)parameters->bitmap.width/(double)parameters->segment_size);
        if (parameters->compression_type == 0)
            parameters->coefficient_count = 2;
        else
            parameters->coefficient_count = 3;

        delete parameters->coefficients;
        parameters->coefficients = new unsigned short[parameters->segment_count*parameters->coefficient_count*3];
        for (int i = 0; i < parameters->segment_count*parameters->coefficient_count*3; i++)
            parameters->coefficients[i] = file.get(8*sizeof(unsigned short));
    }
    //file.save(0, 8*sizeof(unsigned short));       //typ kompresji
    //qDebug() << "parameters of compression";
    //qDebug() << parameters->compression_type;
    char_count = file.get(8*sizeof(unsigned short));
    for (int i = 0; i < 2*255+1; i++)
        statistic[i] = 0;
    //qDebug() << "zero statistic" << char_count;
    for (int i = 0; i < char_count; i++)
    {
        int value = file.get(8*sizeof(short));
        int weight = file.get(8*sizeof(int));
        statistic[value] = weight;
        //qDebug() << value << weight;
    }
    if (root != NULL)
        root->delete_tree(root);
    //qDebug() << "statistic";
    create_tree();
    //print_tree(root);
    //qDebug() << "created tree";
    //print_tree(root);
    make_decodes(root, 0, 0);
    //qDebug() << "decodes";

    dedata = new short[parameters->bitmap.height*parameters->bitmap.width*3];
    int tmp, bite, value, bit_read;
    bool decoded;
    for (int i = 0; i < parameters->bitmap.height*parameters->bitmap.width*3; i++)
    {
        tmp = 0;
        value = 0;
        decoded = false;
        bit_read = 1;
        //qDebug() << "before get";
        bite = file.get(1);
        //qDebug() << bite;
        //qDebug() << "after get";
        if (bite == 0)
            value = value*2;
        else
            value = value*2+1;

        if (dekey.contains(value))
        {
            QList <short> bit = bits.values(value);
            for (int j = 0; j < bit.size(); j++)
                if (bit.at(j) == bit_read)
                    decoded = true;
        }
        /*
            qDebug() << "not contains before";
        else
            qDebug() << "contains before";
        if (!(bits.value(value) == bit_read))
            qDebug() << "not bit before";
        else
            qDebug() << "bit before";
        */
        //qDebug() << !dekey.contains(value) << !(bits.contains(value)) << !(bits.value(value) == bit_read);
        while (!decoded)     //&& bits.contains(value)
        {
            //qDebug() << "while";
            bite = file.get(1);
            //qDebug() << bite;
            bit_read++;
            if (bite == 0)
                value = value*2;
            else
                value = value*2+1;
            if (dekey.contains(value))
            {
                //qDebug() << "contains";
                QList <short> bit = bits.values(value);
                for (int j = 0; j < bit.size(); j++)
                    if (bit.at(j) == bit_read)
                    {
                        //qDebug() << bit.at(j);
                        decoded = true;
                    }
            }
            /*
            if (!dekey.contains(value))
                qDebug() << "not contains";
            else
                qDebug() << "contains";
            if (!(bits.value(value) == bit_read))
                qDebug() << "not bit";
            else
                qDebug() << "bit";
            qDebug() << value;
            */
        }
        //qDebug() << "after while";
        QList <short> bit = bits.values(value);
        for (int j = 0; j < bit.size(); j++)
            if (bit.at(j) == bit_read)
            {
                QList<short> val = dekey.values(value);
                dedata[i] = val.at(j);
            }
        //data[i] = dekey.value(value);
        //qDebug() << i << data[i] << value << bit_read;
    }
    file.close();
}

void huffman_coder::make_decodes(node *root, int value, short bites)
{
    //qDebug() << value << bits;
    if ((root->left == NULL) && (root->right == NULL))
    {
        dekey.insert(value, root->value);
        bits.insert(value, bites);
        //qDebug() << value << bites;
    }
    else
    {
        bites++;
        if (root->left != NULL)
            make_decodes(root->left, 2*value, bites);
        if (root->right != NULL)
            make_decodes(root->right, 2*value+1, bites);
    }
}

short *huffman_coder::decompress(predictor_header *predictor, QString file)
{
    parameters = predictor;
    //delete parameters->coefficients;
    //data = raw_data;
    delete dedata;
    dedata = NULL;
    path = file;
    dekey.clear();
    bits.clear();
    decompress_from_file();
    //raw_data = data;
    return dedata;
}
